#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/unique-paths-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/unique-paths-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

//提交了四次 因为边界问题没有弄好
int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) {

    int col = obstacleGrid[0].size();
    int row = obstacleGrid.size();

    vector<vector<int>> dp(row, vector<int>(col, 0));

    for (int i = 0; i < col && obstacleGrid[0][i] != 1; ++i) {
        //注意边界问题obstacleGrid[0][0]!=1 否则直接break
        dp[0][i] = 1; //我原来这个是赋值-1的 总感觉和原来数组重复了其实没有重复的
    }
    for (int i = 0; i < row && obstacleGrid[i][0] != 1; ++i) {
        //注意边界问题obstacleGrid[0][0]!=1 否则直接break
        dp[i][0] = 1;
    }

    for (int i = 1; i < row; ++i) {

        for (int j = 1; j < col; ++j) {

            //我是这样写的 我感觉好理解
//            if (obstacleGrid[i][j]!=1&&obstacleGrid[i-1][j]!=1)
//                dp[i][j]+=dp[i-1][j];
//             if(obstacleGrid[i][j]!=1&&obstacleGrid[i][j-1]!=1)
//                 dp[i][j]+=dp[i][j-1];

            if (obstacleGrid[i][j] == 1) continue;
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

        }

    }


    return dp[row - 1][col - 1];
}